Được xây dựng từ năm 1865, đường Hải Phòng cùng đường Nathan là hai con đường đầu tiên ở Tiêm Sa Chủy.[2] Con đường ban đầu mang tên Elgin nhưng đến năm 1909 đã đổi thành Hải Phòng,[3] được đặt tên theo thành phố cảng ở Việt Nam để tránh nhầm lẫn với Đường Elgin trên Đảo Hồng Kông. Trong lần đổi tên này nhiều con đường được đặt tên theo các thành phố có buôn bán với Hồng Kông, trong đó có hai con đường khác được đặt tên theo các địa danh Việt Nam là Hà Nội và Sài Gòn.[3] Đây là một trong những đường duy nhất ở Hồng Kông không được đặt tên theo các địa danh ở Trung Quốc hay Anh quốc[2]. Trong thập niên 1920, nhiều thương gia Ấn Độ, hầu hết từ tỉnh Sindh, bắt đầu mở nhiều tiệm trên đường, phục vụ hàng hóa Ấn Độ cho lính đang đóng quân tại Doanh trại Whitfield ở gần đó (nay là Công viên Cửu Long).[4]

Trong thế kỷ đầu tiên sau khi xây dựng, con đường ít được sử dụng, và mãi đến thập niên 1960 nó mới trở nên sầm uất. Một số tòa nhà từ những ngày đầu vẫn còn tồn tại như đền thờ thổ địa và trại lính, nhưng số nhà còn lại được xây sau Thế chiến thứ hai.[2]